/**
 * 
 */
package leetCode;

import java.util.Arrays;

/**
 * @author zhong
 *
 */
public class CarFleet {
	class Car implements Comparable<Car> {
		double speed;
		double position;

		public Car(int position, int speed) {
			this.position = position;
			this.speed = speed;
		}

		@Override
		public int compareTo(Car o) {
			return (int) (this.position - o.position);
		}

	}

	public int carFleet(int target, int[] position, int[] speed) {
		int n = speed.length;
		Car[] cars = new Car[n];
		for (int i = 0; i < speed.length; i++) {
			cars[i] = new Car(position[i], speed[i]);
		}
		Arrays.sort(cars);
		int res = n;
		for (int i = 0; i < cars.length; i++) {
			double minT = Integer.MAX_VALUE;
			for (int j = i + 1; j < cars.length; j++) {
				if (cars[i].speed <= cars[j].speed)// 不可能追上
					continue;
				double t = (cars[i].position - cars[j].position) / (cars[j].speed - cars[i].speed);
				if (t > 0) {
					if (minT > t) {
						minT = t;
					}
				}
			}
			double x = cars[i].speed * minT + cars[i].position;
			if (x <= target) {
				res--;
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int target = 20;
		int[] position = { 6, 2, 17 }, speed = { 3, 9, 2 };
		System.out.println(new CarFleet().carFleet(target, position, speed));
	}

}
